/*================================================================
*   文件名称：main.cpp
*   创 建 者：yang qiang
*   创建日期：2020年08月16日
*   版    本：v1.0.0
*   描    述：
*   Copyright (C) 2020 All rights reserved.
*   
* ================================================================*/


#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    /*
     * @param A: An integer array
     * @param target: An integer
     * @return: An integer
     */
    int MinAdjustmentCost(vector<int> &A, int target) {
        // write your code here
        int size = A.size();
        int maxA = getMax(A);
        vector<vector<int>> dp(size, vector<int>(maxA+1, INT32_MAX));
        for(int i = 0; i < size; i++){
            for(int j = 1; j <= maxA; j++){
                if(i == 0){
                    dp[i][j] = abs(j - A[i]);
                }else{
                    for(int k = max(1, j-target); k <= min(maxA, j+target); k++){
                        dp[i][j] = min(dp[i][j], dp[i-1][k]+abs(j-A[i]));
                    }
                }
            }
        }

        int res = INT32_MAX;
        for(int i = 0; i <=maxA; i++){
            res = min(res, dp[size-1][i]);
        }

        return res;
    }

    int getMax(vector<int> &A){
        int size = A.size();
        int maxres = 0;
        for(int i = 0; i < size; i++){
            maxres = max(maxres, A[i]);
        }

        return maxres;
    }
};

int main(){
    vector<int> A = {3,5,4,7};
    Solution a;
    cout<< a.MinAdjustmentCost(A, 2) <<endl;
    return 0;
}